1212. Бесконечная последовательность 2

Определим бесконечную последовательность А следующим образом:

По заданным значениям n, p, q, x, y вычислите A_n.

Вход. Пять целых чисел n, p, q, x, y (0 £ n £ 10¹³, 2 £ p, q £ 10⁹, 0 £ x, y £ 10⁹).

Выход. Выведите значение A_n.

Пример входа 1	Пример выхода 1
12 2 3 1 0	8
Пример входа 2	Пример выхода 2
10000000 2 3 10000000 10000000	2

РЕШЕНИЕ

рекурсия

Анализ алгоритма

Поскольку n £ 10¹³, хранение всех значений A_i (i = 0, 1, …, n) невозможно ни с использованием массива, ни с помощью структуры map из-за ограничений по памяти. Поэтому для вычислений будем использовать рекурсию, заданную в рекуррентном соотношении.

При этом значения A_i для которых i < 5000000, будем сохранять в массиве m, чтобы избежать повторных вычислений и ускорить выполнение программы.

Реализация алгоритма

Для хранения значений A_i (i < 5000000) объявим массив m.

#define MAX 5000000

long long m[MAX];

Функция f вычисляет значение A_n.

long long f(long long n, long long p, long long q,

long long x, long long y)

{

Если n £ 0, то A_n = 1.

if (n <= 0) return 1;

Если n < 5000000 и значение m[n] уже вычислено (отлично от нуля), то возвращаем его.

if ((n < MAX) && m[n]) return m[n];

Выполняем рекурсивное вычисление значения A_n в соответствии с формулой, приведённой в условии задачи.

long long temp = f(n/p-x,p,q,x,y) + f(n/q-y,p,q,x,y);

Если n < 5000000, сохраняем результат A_n в массиве m, чтобы избежать повторных вычислений в будущем.

if (n < MAX) m[n] = temp;

return temp;

}

Основная часть программы. Читаем входные данные.

scanf("%lld %lld %lld %lld %lld",&n,&p,&q,&x,&y);

Вычисляем и выводим ответ.

res = f(n,p,q,x,y);

printf("%lld\n",res);

Java реализация

import java.util.*;

public class Main

{

static int MAX = 5000000;

static long m[] = new long[MAX];

public static long f(long n, long p, long q, long x, long y)

{

if (n <= 0) return 1;

if (n < MAX && m[(int)n] > 0) return m[(int)n];

long temp = f(n/p-x,p,q,x,y) + f(n/q-y,p,q,x,y);

if (n < MAX) m[(int)n] = temp;

return temp;

}

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

long n = con.nextLong();

long p = con.nextLong();

long q = con.nextLong();

long x = con.nextLong();

long y = con.nextLong();

long res = f(n,p,q,x,y);

System.out.println(res);

con.close();

}

}

Python реализация

Для хранения значений A_i (i < 5000000) объявим список m.

MAX = 5000000

m = [0] * MAX

Функция f вычисляет значение A_n.

def f(n, p, q, x, y):

Если n £ 0, то A_n = 1.

if n <= 0:

return 1

Если n < 5000000 и значение m[n] уже вычислено (отлично от нуля), то возвращаем его.

if n < MAX and m[n]:

return m[n]

Выполняем рекурсивное вычисление значения A_n в соответствии с формулой, приведённой в условии задачи.

temp = f(n // p - x, p, q, x, y) + f(n // q - y, p, q, x, y)

Если n < 5000000, сохраняем результат A_n в массиве m, чтобы избежать повторных вычислений в будущем.

if n < MAX: m[n] = temp

return temp

Основная часть программы. Читаем входные данные.

n, p, q, x, y = map(int, input().split())

Вычисляем и выводим ответ.

res = f(n, p, q, x, y)

print(res)